00100	Many  of  us now believe that robotics will ultimately transform much
00200	of industry; we cannot estimate how rapidly this change will  happen,
00300	but  we  expect  a beginning within a decade, and considerable effect
00400	over a few decades.   Initially, touch, simple  vision  and  computer
00500	control  can  incrementally improve industrial manipulators which now
00600	have no sensing and no  contingency  actions.     In  the  industrial
00700	context,  visual  feedback  functions in constrained situations, with
00800	known objects and background , and approximately known  position  and
00900	orientation,  for  alignment  of  screws with holes, mating surfaces,
01000	etc.   Not only is this problem area of technological importance, but
01100	visual  feedback is a useful paradigm for research.   Current efforts
01200	in  artificial  intelligence  concentrate  on  goal-oriented   visual
01300	systems which take advantage of knowledge of the environment.
01400	
01500	For  robots  to  be highly effective in assembly and other industrial
01600	tasks, their programming for new tasks must be made simple and rapid.
01700	Of  course,  even  if  programming  is  difficult, there will be many
01800	applications  for  which  it  is  useful  to  stockpile  programs  of
01900	production  operations  rather than stockpile parts. But for ultimate
02000	impact, the programming of assembly devices is of great importance. A
02100	mini-computer   to   control  an  assembly  device  is  adequate  for
02200	manipulation and simple visual operations.  Programming tasks for the
02300	assembly  robot  can  be  done  on  a  central  time-sharing computer
02400	facility with large memory,  file  storage,  advanced  languages  and
02500	graphics.  That system could be an internal system for scheduling and
02600	production control, or an external  service.       For  this  primary
02700	problem  in  robotics,  the  whole  of  AI  research is available for
02800	application,  and  the  most  sophisticated  robotics   research   is
02900	relevant.
03000	
03100	But  on  a broader scale, the computerization of industry will affect
03200	production on a shorter time  scale  and  equally  profoundly.    The
03300	problems  under  consideration in AI and the representations of shape
03400	and space which are evolving, have great relevance to the  impact  of
03500	information  science  on  production.           The most far-reaching
03600	consequences will come from intellectual  economies  of  scale  which
03700	follow from systematizing production control, from modularization and
03800	commonality  of  parts  and  operations,  typified  by   the   "group
03900	technology"  approach of Opits.  In this analysis, parts are coded by
04000	descriptors; facilities are reorganized to produce  similar  elements
04100	in  the same facilities.   More generally, the availability of design
04200	records makes possible identification of common parts and  processes,
04300	and  possibility for redesign.   These abilities rest upon facilities
04400	for  design   automation,   description   of   parts   and   objects,
04500	communication  and  filing,  scheduling,  routing,  and  sensing  and
04600	monitoring of production.    Implicit in all this is the  ability  to
04700	represent objects and operations symbolically.
04800	
04900	Minsky and Papert [Minsky 1972] have described the central issues and
05000	the relevance of robotics in artificial intelligence.   These  issues
05100	in intelligence are emphasized:
05200		symbolic descriptions of facts and computational processes
05300		manipulation of descriptions
05400		heterarchical control structures--problem-solving  controlled
05500			by heuristics which depend on the meanings of events.
05600	Our concern is implementation of symbolic descriptions of  shape  and
05700	space  which  are  adequate for integrated robot systems.   We do not
05800	think a single representation is adequate throughout a system, but we
05900	have  attempted to analyze tasks in terms of computational primitives
06000	(originating from topological and geometrical primitives  as  in  the
06100	computational geometry scheme of Minsky and Papert [Minsky 1969]) and
06200	design representation abilities accordingly.     Representative tasks
06300	are manipulation, avoidance, display, and recognition.   Manipulation
06400	requires mass and  moments  of  articulated  parts,  and  ability  to
06500	calculate  overall  moments  in  various  positions and orientations.
06600	Collision  avoidance  in  manipulation   requires   three-dimensional
06700	proximity,  to find objects near a trajectory or near an object to be
06800	grasped.   Display requires description of surface properties and two
06900	dimensional  proximity,  to  find  overlapping surfaces in the image.
07000	Recognition requires visual  memory  for  generation  of  hypotheses,
07100	prediction  and  verification  facilities,  geometric relations among
07200	parts, and a good choice of parts.
07300	
07400	We haven't space for a survey of all research  in  integrated  visual
07500	systems,  nor to discuss modules for three-dimensional interpretation
07600	of line  drawings,  edge  and  region  description,  corner  finding,
07700	prediction,  etc.  We  will  concentrate  on  relating  progress in
07800	description of complex objects and its relevance to  complete  visual
07900	systems.   Figures 1 through 3 show experimental results for computer
08000	description of some objects, from  a  program  by  Agin  at  Stanford
08100	[Agin].    The  program  creates  intuitively natural descriptions of
08200	parts for objects such  as  those  shown.    The  description  system
08300	depends  on  representations  designed  by  te author, and on a laser
08400	triangulation system described by the author and implemented by Agin.
08500	
08600	Although many would disagree about criteria for  representation,  and
08700	although  other  types  of  representations  have  various uses in an
08800	integrated system, the desiderata for representations were:
08900	
09000	a)	Level of Representation
09100	Representations  should  be  chosen  at  a  symbolic level resembling
09200	intuitive descriptions in order to interface with heuristics  of  the
09300	problem domain.    Low level representations should be generated from
09400	the high level representation, or referenced as  special  cases  from
09500	the high level representation.
09600	
09700	b)	Segmentation
09800	Representations should depend  on  segmentation  of  an  object  into
09900	parts.   The parts themselves may be segmented into subparts to allow
10000	levels of detail.  The value of this segmentation depends entirely on
10100	the choice of primitives and the segmentation procedures.
10200	
10300	c)	Primitives
10400	Primitives   should   be   three-dimensional    and    body-centered.
10500	Translational   and   rotational   invariance   are   possible  as  a
10600	consequence. Representations should have  volume  primitives.  Assume
10700	that  we  mean  by  a  primitive  something which is represented by a
10800	description  continuous   in   a   natural   sense   given   by   the
10900	representation.      Then surface primitives do not correspond to the
11000	parts we conveniently think of when we segment an object.  A  surface
11100	primitive  would  be  a continuous surface, eg the soles of our feet,
11200	instead of the feet  themselves.    Rather,  we  think  in  terms  of
11300	arm-like  pieces.  Intuitively,  it seems natural that representation
11400	primitives have the same  dimension  as  the  structure  represented,
11500	allowing  a  finite  covering,  not  a  lower  dimension  requiring a
11600	non-denumerable covering.  To correspond to objects,  representations
11700	must  be  realizable,  that  is,  closed and non-intersecting.    The
11800	primitives we have proposed are  locally  realizable,  that  is,  the
11900	volume  elements are closed and non-intersecting.  Globally, arms may
12000	intersect, however.      Surface  representations,  are  not  locally
12100	realizable,  that  is,  an  infinitesimal element is not closed; only
12200	when we have global information can we test whether  the  surface  is
12300	closed.
12400	
12500	d)	Generative descriptions
12600	Representations should be generative.
12700	That  is,  local primitives should allow a very rich set of shapes to
12800	be conveniently generated.
12900	
13000	THE REPRESENTATION OF SHAPE
13100	
13200	The  representations  [Binford  1971]  depend  upon  segmentation  to
13300	describe  complex  objects in terms of parts. The representations are
13400	graph-structured: nodes correspond to parts, while arcs correspond to
13500	relations  between  parts.     Parts are themselves structures of the
13600	same form.  The relations include relative position and  orientation,
13700	the degrees of freedom, symmetry, and any detailed knowledge of joint
13800	structure.  Examples are neck joint, shoulder joint, and hip joint of
13900	a  human.    Segmentation and graph-structured representation are not
14000	unique; however, their value depends on an  explicit  elaboration  of
14100	primitives which lead to a useful choice of parts.
14200	
14300	The topological operations of cutting and pasting are used in joining
14400	parts.       Normally,  we  think  of  holes  as  made  by  cuts  and
14500	protuberances  as  made by pasting; this can be done purely formally,
14600	but we would like to generalize that to a choice between the  simpler
14700	of  structures,  with cuts or glue.  In fabrication, cutting is often
14800	used to form even complicated  protuberances;  attaching  seems  more
14900	difficult,  particularly when dimensional accuracy is necessary.  The
15000	representation  reflects  some  fabrication  operations,  and  allows
15100	embedding  of  heuristic knowledge.      The representations resemble
15200	construction algorithms.    But we would not expect  that  reasonable
15300	construction   algorithms   could   emerge  until  a  micro-world  of
15400	fabrication operations is available for evaluation of simplicity.
15500	
15600	We have concentrated on the inverse  problem  of  building  up  these
15700	structures  from visual data.  When possible, the choice of parts and
15800	description of joint relations uses whatever knowledge is  available.
15900	When   guesses  are  necessary,  our  heuristics  correspond  to  our
16000	intuition about shape.
16100	
16200	The primitive parts are described by  volume  representations.     We
16300	maintain that a useful choice of parts is in terms of arm-like parts,
16400	which come naturally from the representation. The primitive parts are
16500	described  by "generalized local cones".  These are the volumes swept
16600	out by taking an arbitrary cross section and translating it  along  a
16700	path,  maintaining  the  cross  section normal to the path, while the
16800	scale of the cross section is changed smoothly. More  generally,  we
16900	describe   shapes   generated   from   arbitrary  cross  sections  by
17000	infinitesimal transformations including translations compounded  with
17100	scaling,  rotations,  and  shape  changing  operations applied to the
17200	cross sections.   The basis of this representation is the description
17300	of  a  large  class  of  shapes  based  on  transformation  of  local
17400	descriptions.    The typical element is a snake-like piece, described
17500	by an axis (which is a space curve) and normal cross sections.    The
17600	cross sections are arbitrary.    Local cylinders, cones, toroids, and
17700	helices, all with arbitrary cross sections, are typical examples.
17800	
17900	The process of segmentation allows non-unique representations.   This
18000	permits a choice of simple representations; we can regard  it  as  an
18100	advantage  that we have such a choice. We have a simplicity criterion
18200	of shapes based on the transformation function on the  cross  section
18300	(constant=cylinder,  linear=cone,  monotonic, convex, single maximum,
18400	shape changing...).  As an example:
18500	
18600	
18700	
18800				MAN
18900				
19000			       [HEAD]
19100				 |
19200				NECK
19300				 |
19400		      [ARM]--<SHOULDERS>--[ARM]
19500				 |
19600			       TRUNK
19700				 |
19800			      <HIPS>
19900			      |    |
20000			  [LEG]    [LEG]
20100	
20200	
20300	
20400	
20500	
20600	where brackets indicate complex parts and <> indicate joints.
20700	ARM is:		ARM
20800	
20900			     UPPER ARM
21000				|
21100			      <ELBOW>
21200				|
21300			     FOREARM
21400				|
21500			     <WRIST>
21600				|
21700			      <HAND>
21800		  |	   |	    |	      |	      |
21900		[FINGER] [FINGER] [FINGER] [FINGER] [THUMB]
22000	
22100	
22200	
22300	A primitive has the representation:
22400	
22500			FOREARM
22600		    |	  |      |
22700		CROSS	AXIS	TRANSFORMATION
22800	       SECTION
22900	
23000	The  primary  considerations  for  the  utility of the representation
23100	concern the tasks we will need to  perform.     These  tasks  can  be
23200	described in various ways; the most enlightening description of tasks
23300	is in terms of their computational structure.   For  these  problems,
23400	topological  and  geometric  considerations  are  important.  Surface
23500	representations have been used for display purposes.    For  robotics
23600	applications,  the representation for manipulation would need to make
23700	explicit how to pick up an object, i.e. where is the center of  mass,
23800	the  center  of rotation, and what are the moments.  How thick is the
23900	piece, and how long?  These are more than  just  surface  properties,
24000	and  the  surface  representation  is  no  help  in determining these
24100	properties. These properties are the sort  of  properties  which  are
24200	natural  for  our  volume representations; however surface properties
24300	are quite naturally obtained in this representation.
24400	
24500	The cross sections  are  represented  in  the  same  fashion  in  two
24600	dimensions  as  objects  are  in  three  dimensions.   The part/whole
24700	segmentation is crucial.    The parts which are useful are  not  just
24800	curves,  but  arm-like  areas.    Thus  we  are  interested  in  area
24900	representations, not curve representations. The descriptions in terms
25000	of  a two-dimensional axis and normal width are similar to the volume
25100	representations described by a space curve and normal cross section.
25200	
25300			CROSS SECTION
25400		[AREA-PART]--<JOINT>--[AREA-PART]
25500	
25600	
25700	where a part of a cross section is an area defined by  subparts.    A
25800	primitive area-part is defined by:
25900			    PRIMITIVE AREA-PART
26000			|	|	|	|
26100		     WIDTH    AXIS   TRANS   SURFACE
26200					     PROPERTIES
26300	
26400	
26500	The  coordinate  system is local to each element.  Each link connects
26600	two joints.  Each link contains a transformation required to go  from
26700	the  coordinate  system of an element at one joint, to the coordinate
26800	system of an element at  the  other  joint.  This  is  a  translation
26900	combined  with a rotation.  It is most convenient to define the local
27000	coordinates in terms of actual vectors rather than with an  arbitrary
27100	basis.
27200	
27300	DEPTH MEASUREMENT TECHNIQUES
27400	
27500	The human visual system uses both stereo and motion parallax to  gain
27600	depth  information.   The two function in approximately the same way.
27700	With stereo, the images seen by the two eyes are nearly alike.   With
27800	motion  parallax,  successive  images  are  nearly  alike.   Thus, to
27900	correspond a point in one image with a point in the other,  a  search
28000	over a small range is necessary.  With motion parallax, corresponding
28100	points can be tracked through successive images to  achieve  a  large
28200	baseline,  and  depth  resolution at large distances.  Relative depth
28300	information (ie one point nearer by two  inches)  requires  only  the
28400	shift  between  correspondences.  Motion parallax was used by Nevatia
28500	[Nevatia] to measure depth of points on samples of rocks.  With a  50
28600	mm  lens and a 5 degree baseline at a meter, depth accuracy was about
28700	2 mm. This was measured for a cup with circular cross section.   That
28800	correspondence   error   is  about  1/8  th  tv  picture  cell.   The
28900	corresponding phenomenon is noted  in  human  vision  in  stereo  and
29000	vernier  acuity.    It  has a straightforward explanation in terms of
29100	expected errors based on the correlation process.
29200	
29300	Work is underway at several laboratories on stereo correlation. [Quam
29400	1972].    Current  programs  are  inadequate  conceptually  at  depth
29500	discontinuities and with respect to ambiguities; they  require  about
29600	20  minutes with PDP-10 class machines.  There are major improvements
29700	which can be made in the strategies for correspondence,  and  factors
29800	of  approximately  100  in  speed  can  be gained by low cost special
29900	purpose visual processors.
30000	
30100	Laser depth ranging hardware has been  operating  at  Stanford  since
30200	January,  1971[Agin].   As  in stereo, we know the angles of the rays
30300	from the laser to the object, and from the object to the camera. Thus
30400	we  know  the baseline and two angles of a triangle, which completely
30500	determines the position of the object illuminated by the  laser.   As
30600	shown  in  figure  4,  the  laser  beam  is diverged into a plane, to
30700	simplify the deflection sytem to one dimension, and speed data taking
30800	without  introducing  ambiguity. Each ray from the laser appears at a
30900	unique angle in the video image. The approximate depth resolution  is
31000	about 1 mm at 1 meter.  The limit on the speed of reading is about 20
31100	scans per second, with about 100  scans  required  for  a  reasonable
31200	resolution.    That  scan  time  is  shorter  than  the corresponding
31300	computation time.  The laser  required  to  operate  with  a  silicon
31400	vidicon tube costs only about $250.
31500	
31600	Other  techniques  are  described  in  a sensor study [Binford 1972].
31700	Ultrasonics have too slow a sample rate.  Most other techniques are a
31800	form  of  triangulation  as  in  the  laser system just described, or
31900	measure the time of flight or phase change of modulated signals  over
32000	the  flight  time.    Since light travels at 1 ft per nanosecond, the
32100	measurement of 1 mm resolution requires 2 picosecond time resolution.
32200	Presently,  most  optical  depth-measuring  techniques have speed and
32300	resolution more appropriate for surveying or vehicle navigation  than
32400	computer-controlled  assembly,  but  techniques exist for substantial
32500	improvement.
32600	
32700		TECHNIQUES OF DESCRIPTION
32800	
32900	We describe briefly some of the work from Agin's thesis  [Agin].  The
33000	plane  of  the laser beam intersects objects along space curves which
33100	project as curves from the viewpoint of the camera. These  are  shown
33200	in  figure  5.     Depth discontinuities in space appear as breaks in
33300	the curve in the image and slope discontinuities in space  appear  as
33400	slope discontinuities in the image.  In the representation, parts are
33500	defined by continuity of axis and normal cross  section.    The  path
33600	through  corresponding points (midpoints) of cross sections should be
33700	everywhere normal to the cross sections. That calculation  is  stable
33800	for successive approximation. Some spurious local axes are removed by
33900	extending local  axis  descriptions  to  impose  continuity.    There
34000	remain  some  parts  which  are  described  in  several ways.   These
34100	alternate descriptions must be evaluated by a more global choice.
34200	
34300	To find good starting points for local axis descriptions, portions of
34400	objects  are  found  for  which  the scan cross sections (usually not
34500	normal to the eventual axis) are smoothly changing and  overlap.   An
34600	estimate  of  the  axis  for  the  group  is  made  by connecting the
34700	midpoints of  scan  cross  sections.     The  midpoints  are  a  good
34800	approximation  to  the axis even when the scan is relatively far from
34900	normal to the axis.   Axis estimates from preliminary groupings for a
35000	doll  are shown in figure 6.   The approximate axis gives an estimate
35100	for the directions of normal cross sections, which in  turn  give  an
35200	improved axis estimate.  The process quickly gives an axis determined
35300	by normal cross sections.   The pieces are thus  described  as  local
35400	"generalized  cones".   An  estimate  is  made  of  the cross section
35500	function, and the cone is extended by another  iterative  description
35600	process.    Eventually,  when  the  description is extended as far as
35700	possible, it is broken off.   The condition for breaking off is  that
35800	the cross section function must fit a parabola well over the whole of
35900	the axis.  Figures 1 through 3 show the  descriptions  of  parts  for
36000	some objects.  Because the program does not have good representations
36100	of the boundaries,  the  crude  tests  for  cross  sections  crossing
36200	boundaries  are  sometimes  inadequate,  and  two parts may be linked
36300	together, causing some gross errors in description of parts.    These
36400	operations  are  performed  in  three-dimensions,  and circular cross
36500	sections are assumed.   The assumpton of circular cross  sections  is
36600	only an expedient and not at all fundamental to the method.
36700	
36800	For  objects  consisting  of  one  part, such as a ring or snake, the
36900	descriptions are quite natural.  A ring is described as an element of
37000	constant  cross  section  along  a  closed,  circular  axis.     More
37100	complicated objects with several parts have  reasonable  descriptions
37200	of the parts, but the parts are not connected together, so that there
37300	is no sense of complete structure.
37400	
37500		CURRENT DIRECTIONS
37600	
37700	The  description  techniques  have  exemplified   the   idea   of   a
37800	computational    equivalent   to   a   representation.    Parts   are
37900	characterized by  continuous  axis  direction  and  continuous  cross
38000	sections.   In  generalizing  the  class  of  cross sections, another
38100	direct computational realization  emerged:  the  realization  of  the
38200	representation  in  terms  of  "generalized translational invariance"
38300	[Binford].
38400	
38500	The descriptions are intended for recognition,  among  other  things.
38600	To  that  end,  the  current  work  is  involved  in forming complete
38700	descriptions of objects, linking parts together at  joints,  choosing
38800	among  alternative descriptions. The paradigm is recognition from the
38900	system's own descriptions  among  a  potentially  very  large  visual
39000	memory.  The techniques of visual memory are closely coupled to these
39100	symbolic descriptions and will be described in forthcoming work.
39200	
39300	
39400	We  have  discussed representation and description without mentioning
39500	statistical learning.     We think that structured learning  is  more
39600	relevant,  and  that  the  best examples of learning schema have been
39700	Winston's [Winston].     Instead of many trial learning, that  system
39800	learned significant new structures on a single trial learning.    But
39900	the  essential  difference  from  statistical  schemes  is  that  the
40000	learning consisted in building up symbolic descriptions, manipulating
40100	them and comparing them.  Instead of examples  contributing  to  some
40200	diffuse  evaluation  function,  comparison  of an example description
40300	with the concept  description  causes  modification  of  the  concept
40400	description  specific  to the differences. What types of descriptions
40500	are useful?     Winston's work was successful because his  primitives
40600	were    geometric    relations    like    left/right,    above/below,
40700	supporting/supported-by, etc, and he was able to express  interesting
40800	concepts  of  geometric  structures  as  simple combinations of these
40900	geometric relations.  We aim for an extension of these ideas with  an
41000	understanding  of  form  and  its semantics, as expressed in a richer
41100	description of form and relations. The ability to  make  descriptions
41200	and  modify them enables the system to remember objects.  There is no
41300	description of procedures and ability to  modify  such  descriptions;
41400	consequently,  the  system cannot learn about how to perceive complex
41500	objects.
     

00100	[Anderson 1972] R. Anderson,"Programmable Automation, The Future
00200	of Computers in Manufacturing", Datamation, Dec 1972.
00300	
00400	[Agin] G. Agin, "Description and Representation of  Curved  Objects",
00500	Ph.D.  Thesis, Computer Science Dept., Stanford University, September
00600	1972.
00700	
00800	
00900	[Binford 1972]"Sensor Systems for  Manipulation",  Conference  on  Remotely  Manned
01000	Systems, JPL, Pasadena, Calif, Sept 1972.
01100	
01200	[Binford 1971] "Visual  Perception  by  Computer",  Invited  paper  at  IEEE Systems
01300	Science and Cybernetics, Miami, Dec 1971.
01400	
01500	
01600	
01700	[Minsky 1972] "Artificial Intelligence Progress Report", AI Memo 252,
01800	MIT AI Lab, (1972);
01900	
02000	[Minsky 1969] M.L.Minsky and S.Papert, "Perceptrons", MIT Press,
02100	Cambridge, Mass, 1969.
02200	
02300	
02400	[Quam 1972] L. H. Quam, S. Liebes, Jr., R. B. Tucker, M.  J.  Hannah,
02500	B.  G.  Eross,  "Computer  Interactive  Picture Processing", Stanford
02600	Artificial Intelligence Laboratory AIM-166, April 1972.
02700	
02800	
02900	[Winston 1970] Winston, P.H.,"Learning Structural Descriptions from
03000	Examples", AI Technical Report 231, Artificial Intelligence Laboratory,
03100	MIT, September 1970.